#include <stack>
#include <vector>

using namespace std;

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stack;
        int index = 0;
        for (int& push : pushed) {
            stack.push(push);
            while (!stack.empty() && stack.top() == popped[index]) {
                stack.pop();
                index++;
            }
        }
        return index == popped.size();
    }
};

int main() {
    vector<int> pushed = {1,2,3,4,5}; vector<int> popped = {4,5,3,2,1};
    Solution solution;
    solution.validateStackSequences(pushed, popped);
    return 0;
}
